Data communication in a computer network involves the exchange of data between two or more entities interconnected by communication links and subnetworks. These entities are typically software programs executing on hardware computer platforms, which, depending on their roles within the network, may serve as end stations or intermediate stations. Examples of intermediate stations include routers, bridges and switches that interconnect communication links and subnetworks; an end station may be a computer located on one of the subnetworks. More generally, an end station connotes a source of or target for data that typically does not provide routing or other services to other computers on the network. A local area network (LAN) is an example of a subnetwork that provides relatively short-distance communication among the interconnected stations; in contrast, a wide area network (WAN) facilitates long-distance communication over links provided by public or private telecommunications facilities.
End stations typically communicate by exchanging discrete packets or frames of data according to predefined protocols. In this context, a protocol represents a set of rules defining how the stations interact with each other to transfer data. Such interaction is simple within a LAN, since these are typically "broadcast" networks: when a source station transmits a frame over the LAN, it reaches all stations on that LAN. If the intended recipient of the frame is connected to another network, the frame is passed over a routing device to that other network. Collectively, these hardware and software components comprise a communications network and their interconnections are defined by an underlying architecture.
Traffic flowing through a network may be considered as a set of flows. A flow consists of a set of packets that require similar treatment by the network. Flows may be defined according to a wide range of criteria to meet different needs. For example, a flow could be the set of packets sent from one host to another, or it could be the set of packets exchanged by a pair of communicating application programs. In general there may be many flows passing through any point in the network at any time.
Packets travel between network entities over "circuits" connecting the entities. The traditional circuit is a physical transmission line between the communicating stations, and over which data is exchanged. The circuit is defined by a communication subnetwork that carries messages between connected entities the way the telephone system connects callers--i.e., over wires or optical fibers intercommunicating through switches. Accordingly, the physical circuit is continuously dedicated to the transmission path between connected entities; data exchange is synchronous over the path in the sense of being tied to a common master clock.
This mode of communication absorbs substantial bandwidth. Unless data moves constantly between the communicating entities, the circuit will at times be idle and the bandwidth consequently wasted. To avoid this, networks frequently employ "virtual" circuits rather than dedicated transmission lines. The virtual circuit establishes a routing pathway for message travel between communicating stations, and is virtual in the sense that many stations can transmit across the lines defining the circuit; these are not dedicated to a single pair of entities. Different types of networks employ the virtual circuit (VC) model of communication, most notably Frame Relay and Asynchronous Transfer Mode (ATM).
ATM can accommodate constant-rate and variable-rate data traffic. The VC may be established by a SETUP message, which travels through a sequence of switches until it reaches the destination station, thereby establishing the VC path. In general, a VC may carry many flows at one time.
A representative ATM configuration is shown in FIG. 1. A single VC interconnects router 25 and router 27. An end station 10 on a LAN 12 communicates with an end station 15 on another LAN 17 over this VC, and with an end station 20 on still another LAN 22 over the same VC. The VC in this case carries two flows: one from end station 10 to end station 15, and one from end station 10 to end station 20. The flows are handled by first and second routers 25, 27 and a series of ATM switches representatively indicated at 30, 32. Each router 25, 27 is connected to an illustrated LAN and to an ATM switch. The connection to an ATM switch is by means of an ATM interface configured to direct flows onto VCs; the routers establish further connections by means of additional interfaces, which may or may not be ATM interfaces. That is, each router 25, 27 may contain various interfaces for handling different types of network traffic.
Routers 25, 27 typically forward IP datagrams (i.e., operating at level 3 in the protocol stack by inspecting IP headers), terminating VCs at the ATM interfaces. ATM switches 30, 32 forward ATM cells (operating at level 2 in the protocol stack by examining ATM cell headers). VCs do not terminate on the interfaces of ATM switches 30, 32, instead passing through the switches. The VCs, then, span routers 25, 27, originating on one router and terminating on the other.
There may be more than one VC between router 25 and router 27. Furthermore, there may be additional VCs originating (or terminating) on routers 25, 27 and terminating (or originating) on other routers not shown here.
The foregoing discussion assumes a continuous sequence of ATM switches intervening between ATM-capable routers 25, 27. Other device sequences are of course possible. For example, depending on the routing algorithm and communications costs, router 25 may direct traffic directly to router 27 and vice versa. Alternatively, one or more routers may intervene between ATM switches 30, 32. In this case, communication between end stations 10, 15 and 10, 20 would occur over paths defined by multiple sequential VCs, each terminating at a router.
Permitting communication resources to be shared among many communicating entities may lead to congestion. Routers and links have finite information-handling capacity (bandwidth), and if streams of packets arrive on several input lines all requesting the same output line, a queue will build up. Eventually, if the queue exceeds the buffering capacity of the router, packets will be lost.
One approach to congestion control is "traffic shaping," which regulates the average rate and concentration of data transfer--that is, the traffic pattern. Limitations on transmission patterns are imposed on each VC with the goal of avoiding excessive data backup. These limitations are enforced by a "shaper," usually implemented in hardware running on a router's ATM network interfaces. The pattern adopted by a shaper may differ for different VCs and may also vary over time for a particular VC. If packets arrive at the router above the allowed VC transmission rate, then the network interface "shapes" the traffic sent on the VC to conform to that rate. As a result, packets must be buffered in the router circuitry or on the network interface itself. When this condition occurs, the VC is said to be "backlogged."
Another approach to traffic management is reactive rather than proactive. The bandwidth of the VC cannot be expanded, but at least it can be allocated among flows on the VC. "Fair queueing" is a simple approach to bandwidth allocation in which a queue is defined for each flow seeking access to a given router output line. The router is programmed to scan the queues round robin, sequentially taking the first packet from each queue and transmitting it over the line. A flow, in this circumstance, is a series of packets requiring similar queueing treatment.
One problem with this approach is that it allocates more bandwidth to hosts that transmit large packets. Accordingly, fair queueing is typically implemented on a byte-by-byte, rather than on a packet-by-packet basis. A second problem is that all flows receive the same amount of bandwidth. In many situations, certain flows--such as those carrying critically important data--deserve greater bandwidth than others. A modified approach to fair queueing, called "weighted fair queueing" (WFQ), discriminates among flows by causing the network interface to transmit more bytes from certain queues during each pass, or to return to those queues more often than others.
Shaping and queueing represent different and in some ways complementary approaches to traffic management. Shaping limits traffic in an effort to avoid congestion, but does not attempt to ensure fairness in bandwidth allocation. WFQ criteria, by contrast, operate based on the specified characteristics of the flows rather than congestion on the VCs they use. For example, a packet due for transmission based on WFQ criteria may belong to a backlogged VC, and so cannot or should not be sent.